package TenBasicAlgorithm;

import java.util.Arrays;

//(最短路径问题)（生成各点到其他各点的最短路径更新去每个点的路径和所需要经过的前驱节点名称）(都取最短局部最优有点贪心的感觉)
//重点在求各点到其余各点的最短距离
//三层循环以中间节点去更新相邻的节点距离与前驱关系
public class FloydDemo {
    public static void main(String[] args) {
        char[]vertex={'A','B','C','D','E','F','G'};
        final int N=65535;
        int[][]matrix=new int[vertex.length][vertex.length];
        matrix[0]=new int[]{0,5,7,N,N,N,2};
        matrix[1]=new int[]{5,0,N,9,N,N,3};
        matrix[2]=new int[]{7,N,0,N,8,N,N};
        matrix[3]=new int[]{N,9,N,0,N,4,N};
        matrix[4]=new int[]{N,N,8,N,0,5,4};
        matrix[5]=new int[]{N,N,N,4,5,0,6};
        matrix[6]=new int[]{2,3,N,N,4,6,0};
        FloydGraph floydGraph=new FloydGraph(vertex.length,vertex,matrix);

        floydGraph.floyd();
        floydGraph.show();
    }
}
class FloydGraph{
    private char[] vertex;
    private int[][] dis;
    private int[][] pre;

    public FloydGraph(int length,char[] vertex, int[][] dis) {
        this.vertex = vertex;
        this.dis = dis;
        this.pre=new int[length][length];
        for (int i = 0; i < length; i++) {
            Arrays.fill(pre[i],i);
        }
    }
    public void show(){
        for(int[] link:pre){
            System.out.println(Arrays.toString(link));
        }
        System.out.println();
        for(int[] link:dis){
            System.out.println(Arrays.toString(link));
        }
    }
    public void floyd(){
        int len=0;
        for (int k = 0; k < dis.length; k++) {//中间节点
            for (int i = 0; i < dis.length; i++) {//出发点
                for (int j = 0; j < dis.length; j++) {//终点
                    len=dis[i][k]+dis[k][j];
                    if(len<dis[i][j]){//发现较短路径就更新距离
                        dis[i][j]=len;
                        pre[i][j]= pre[k][j];//更新前驱节点(记录路径)
                    }
                }
            }
        }
    }
}
